Chapter 14 Mathematical Reasoning (Concepts)

Propositions

Mathematical reasoning is the bedrock of all mathematics. It is the rigorous process of using logic to construct arguments, establish facts, and prove new truths. The fundamental unit of any logical argument is a clear, unambiguous sentence called a statement or a proposition.

What is a Statement (Proposition)?

In the language of mathematical logic, a statement is a declarative sentence that can be definitively classified as either true or false, but not both at the same time. A statement must make a clear assertion that can be objectively verified.

The property of being either true or false is called the truth value of the statement. Every statement has a truth value of either True (T) or False (F). The terms "statement" and "proposition" are used interchangeably in this context.

Examples of Sentences that are Statements

To be a statement, a sentence must be a declaration of fact (even if the fact is incorrect) and have a single, unchanging truth value.

1. "New Delhi is the capital of India."

   This is a declarative sentence. It makes a factual claim that is universally accepted as true. Therefore, it is a statement with a truth value of True.

2. "The sum of the angles in a triangle is 180 degrees."

   This is a declarative sentence stating a well-known geometric theorem. It is true. Therefore, it is a statement with a truth value of True.

3. "3 + 7 = 12."

   This is a declarative sentence. It makes a mathematical claim. However, the claim is incorrect, as 3 + 7 = 10. Because the sentence is definitively false, it is still a statement. Its truth value is False.

4. "The Earth is flat."

   This is a declarative sentence. It makes a claim about the shape of the Earth. Based on overwhelming scientific evidence, this claim is false. Therefore, it is a statement with a truth value of False.

Examples of Sentences that are NOT Statements

Many types of sentences that we use in everyday language do not qualify as mathematical statements because they lack a clear, objective truth value.

1. Questions: "Where are you going?"

   This is an interrogative sentence. It seeks information and does not make a claim. It cannot be true or false, so it is not a statement.

2. Commands: "Please complete your homework."

   This is an imperative sentence. It gives an instruction. It is not an assertion of fact, so it is not a statement.

3. Opinions or Exclamations: "Mathematics is a fun subject!"

   This sentence expresses a personal opinion. Its "truth" is subjective and varies from person to person. It cannot be objectively classified as true or false for everyone, so it is not a statement.

4. Open Sentences with Variables: "$x + 2 = 5$."

   This sentence is declarative, but its truth depends on the value of the variable $x$. If $x=3$, the sentence becomes "3 + 2 = 5," which is a true statement. If $x=10$, it becomes "10 + 2 = 5," which is a false statement. Because its truth value is not fixed and depends on an unknown variable, it is an open sentence, not a statement.

5. Ambiguous or Time-Dependent Sentences: "Today is Friday."

   The truth of this sentence depends on when it is spoken. On a Friday it is true, but on any other day it is false. Sentences whose truth value can change with time or context are not considered statements in logic.

6. Paradoxes: "This statement is false."

   This sentence, known as the Liar Paradox, leads to a logical contradiction. If we assume it's true, it must be false. If we assume it's false, it must be true. Since it can be neither true nor false without contradicting itself, it is not a statement.

The Role of Statements in Mathematics

The entire structure of mathematics is built upon statements. Mathematical proofs are logical arguments that begin with a set of statements assumed to be true (called axioms or postulates) and use rules of logic to deduce new, true statements (called theorems). Every step in a proof must be a valid statement with a clear truth value, ensuring that the final conclusion is logically sound and rigorously established.

Negation of a Statement

In mathematical logic, once we have a statement, one of the most basic operations we can perform is to negate it. The negation of a statement is another statement that asserts the exact opposite. It is the logical equivalent of saying "it is not true that..." followed by the original statement.

Definition of Negation

The negation of a statement, let's call it $p$, is a new statement, denoted as $\sim p$ (read as "not p"), which has the opposite truth value of $p$.

• If the original statement $p$ is true, then its negation $\sim p$ must be false.
• If the original statement $p$ is false, then its negation $\sim p$ must be true.

A statement and its negation can never be true at the same time, nor can they both be false at the same time. This relationship is perfectly captured in a simple truth table:

How to Form a Negation

For a simple declarative sentence, forming the negation is often as straightforward as inserting the word "not" in the grammatically correct place. For example:

• Statement: "Paris is in France." (True)
• Negation: "Paris is not in France." (False)

Another way is to preface the original statement with a phrase like "It is not the case that..." or "It is false that...".

• Statement: "2 + 2 = 5." (False)
• Negation: "It is not the case that 2 + 2 = 5." (True)

However, when statements involve words like "all," "some," or "none" (known as quantifiers), forming the correct negation requires more care.

Negating Statements with Quantifiers ("All" and "Some")

Negating statements with quantifiers is a common area of confusion. The key is to understand what it takes to disprove the original statement.

Negating an "All" Statement

Consider the statement: "All dogs are mammals."

To prove this statement is false, you do not need to show that "No dogs are mammals." You only need to find one single counterexample. If you could find just one dog that is not a mammal, the original "All" statement would be false.

Therefore, the logical opposite (the negation) is:

"There exists at least one dog that is not a mammal." or "Some dogs are not mammals."

Rule: The negation of "All A are B" is "Some A are not B."

Negating a "Some" Statement

Consider the statement: "Some students in the class have brown hair."

This statement claims that there is at least one student with brown hair. To prove this is false, you would have to check every single student and confirm that none of them have brown hair. In other words, you would have to show that "All students in the class do not have brown hair."

Therefore, the logical opposite (the negation) is:

"All students in the class do not have brown hair," or "No student in the class has brown hair."

Rule: The negation of "Some A are B" is "No A are B" (or "All A are not B").

Answer:

Answer:

Compound Statements

In our everyday language and in mathematical reasoning, we rarely use simple statements in isolation. We connect ideas and statements to form more complex, meaningful sentences. In logic, when we combine one or more simple statements using specific connecting words, we create what is known as a compound statement.

Definition of a Compound Statement

A compound statement is a statement formed by joining two or more simple statements, called component statements, with special words or phrases called logical connectives.

The most important feature of a compound statement is that its truth value (whether it is true or false) is completely determined by the truth values of its individual component statements and the rules associated with the connective used to join them.

For instance, consider two simple statements:

• Statement p: "It is daytime."
• Statement q: "The sky is blue."

We can combine them to form the compound statement: "It is daytime and the sky is blue." The truth of this new, longer statement depends entirely on whether its two parts are true.

The Basic Logical Connectives

The connecting words that we use to build compound statements are called logical connectives. The five most important connectives in mathematical logic are "AND," "OR," "NOT," "IF...THEN," and "IF AND ONLY IF."

1. "AND" (Conjunction)

When we connect two statements, $p$ and $q$, with the word "and," we form a conjunction. The symbol for this is $\wedge$.

Statement: $p \wedge q$ (read as "p and q")

Rule: The conjunction $p \wedge q$ is true only if both $p$ and $q$ are true. If either $p$ or $q$ (or both) is false, the entire "and" statement is false.

Example: "The number 4 is even and the number 5 is odd." (True $\wedge$ True). This is a True statement.

Example: "The number 4 is even and the number 6 is odd." (True $\wedge$ False). This is a False statement.

2. "OR" (Disjunction)

When we connect two statements, $p$ and $q$, with the word "or," we form a disjunction. The symbol for this is $\vee$.

Statement: $p \vee q$ (read as "p or q")

Important Note: In mathematics, "or" is almost always used in an inclusive sense. This means "p or q" is true if p is true, or if q is true, or if both are true.

Rule: The disjunction $p \vee q$ is false only if both $p$ and $q$ are false. In all other cases, it is true.

Example: "A square has four sides or a triangle has three sides." (True $\vee$ True). This is a True statement.

Example: "A square has five sides or a triangle has three sides." (False $\vee$ True). This is still a True statement because one part is true.

Example: "A square has five sides or a triangle has four sides." (False $\vee$ False). This is a False statement.

3. Other Connectives

We also have other important ways of connecting statements, which will be explored in more detail in later sections:

• Negation ($\sim$): This operator, discussed previously, takes a single statement and reverses its truth value. ("not p")
• Implication ($\implies$): This represents an "if-then" relationship. ("if p, then q")
• Biconditional ($\iff$): This represents an "if and only if" relationship, meaning two statements are logically equivalent. ("p if and only if q")

Example of Evaluating Truth Values

Let's use the following statements:

• Statement p: "Delhi is in India." (Truth value: T)
• Statement q: "2 is a prime number." (Truth value: T)
• Statement r: "A week has 8 days." (Truth value: F)

Now let's evaluate some compound statements:

1. $p \wedge q$: "Delhi is in India and 2 is a prime number."

   This is (T $\wedge$ T). Since both components are true, the compound statement is True.

2. $q \wedge r$: "2 is a prime number and a week has 8 days."

   This is (T $\wedge$ F). Since one component is false, the compound statement is False.

3. $p \vee r$: "Delhi is in India or a week has 8 days."

   This is (T $\vee$ F). Since at least one component is true, the compound statement is True.

4. $\sim p$: "Delhi is not in India."

   This is $\sim$(T). The negation of a true statement is False.

5. $(\sim p) \vee r$: "Delhi is not in India or a week has 8 days."

   This is (F $\vee$ F). Since both components are false, the compound statement is False.

Logical Connectives and Quantifiers

Mathematical reasoning is built by taking simple, true statements (like axioms and definitions) and linking them together in a logical chain to arrive at new, true conclusions (theorems). The "links" in this chain are the logical connectives, and the words that tell us the scope of our statements (e.g., whether they apply to "all" things or just "some") are the quantifiers.

Logical Connectives and Their Truth Tables

Logical connectives are the operators of logic. They take simple statements as inputs and produce a new compound statement whose truth value is determined by a strict set of rules. These rules are most clearly defined using truth tables.

Let's consider two simple statements, $p$ and $q$.

1. Conjunction (AND)

The conjunction of $p$ and $q$, written as $p \wedge q$, is true only when both of its component statements are true. Think of it as a strict requirement: for the whole statement to be true, every part must be true.

Rule: True only when T $\wedge$ T.

2. Disjunction (OR)

The disjunction of $p$ and $q$, written as $p \vee q$, is true if at least one of its component statements is true. In mathematics, this is an inclusive OR, meaning it's also true when both components are true.

Rule: False only when F $\vee$ F.

3. Negation (NOT)

Negation, written as $\sim p$, is the simplest connective. It operates on a single statement and simply flips its truth value.

Rule: T becomes F, and F becomes T.

Quantifiers

Quantifiers transform open sentences (with variables) into statements by specifying "how many" elements a property applies to. They are essential for making general claims in mathematics.

1. The Universal Quantifier ($\forall$) - "For All"

The universal quantifier, $\forall$, is used to assert that a property is true for every single element in a given set. It's a very strong and sweeping claim.

Notation: $\forall x, P(x)$

Meaning: "For every element $x$ in our set, the property $P(x)$ is true."

Example: Let our set be all triangles. Let $P(x)$ be the property "the sum of the angles in triangle $x$ is 180°". The statement "$\forall x, P(x)$" means "For all triangles, the sum of the angles is 180°." This is a true statement.

To prove a "for all" statement is false, you only need to find one counterexample.

2. The Existential Quantifier ($\exists$) - "There Exists"

The existential quantifier, $\exists$, is used to assert that there is at least one element in a given set for which a property is true. It makes a much weaker claim than the universal quantifier.

Notation: $\exists x, P(x)$

Meaning: "There exists at least one element $x$ in our set for which the property $P(x)$ is true."

Example: Let our set be all integers. Let $P(x)$ be the property "$x$ is an even prime number". The statement "$\exists x, P(x)$" means "There exists an integer that is an even prime number." This is a true statement, because the number 2 satisfies this property.

To prove a "there exists" statement is false, you must show that the property is false for every single element in the set.

Connecting Quantifiers and Connectives

Quantifiers can be thought of as shorthands for long compound statements, especially when dealing with finite sets.

• "For all" ($\forall$) is like a long chain of ANDs. The statement "All numbers in the set {2, 4, 6} are even" is logically equivalent to "(2 is even) AND (4 is even) AND (6 is even)". If any one part is false, the whole statement is false.
• "There exists" ($\exists$) is like a long chain of ORs. The statement "Some number in the set {1, 2, 3} is even" is logically equivalent to "(1 is even) OR (2 is even) OR (3 is even)". If any one part is true, the whole statement is true.

Implications

One of the most powerful and common ways to connect statements in mathematics is through an implication, also known as a conditional statement. These are the "if-then" statements that form the backbone of logical deduction and are used to state nearly every theorem in mathematics.

What is an Implication?

An implication is a compound statement that expresses a relationship of consequence between two component statements. It is typically written in the form "If $p$, then $q$".

The standard symbol for this is $p \implies q$ (read as "p implies q").

• The first part, $p$, is called the hypothesis or antecedent. It is the condition or premise we assume to be true.
• The second part, $q$, is called the conclusion or consequent. It is the result that is claimed to follow from the hypothesis.

An implication is like a promise or a contract. The statement "If you get an A on the final exam, then I will buy you a pizza" ($p \implies q$) is a promise. We can use this analogy to understand its truth value.

The Truth Value of an Implication

In mathematical logic, the truth of an "if-then" statement is defined very precisely. It might feel a little different from everyday language, where "if-then" often suggests a cause-and-effect relationship.

The implication $p \implies q$ is considered false in only one situation: when the hypothesis ($p$) is true, but the conclusion ($q$) is false. In every other scenario, the implication is considered true.

Let's use our pizza promise: "If you get an A ($p$), then I will buy you a pizza ($q$)."

1. You get an A (p is True) and I buy you a pizza (q is True).

   I kept my promise. The statement $p \implies q$ is True.

2. You get an A (p is True) and I do not buy you a pizza (q is False).

   I broke my promise. The statement $p \implies q$ is False. This is the only way the promise can be broken.

3. You do not get an A (p is False) and I buy you a pizza anyway (q is True).

   I did not break my promise. The original contract was only about what happens *if* you get an A. Since you didn't, I am free to do whatever I want. The promise remains intact. The statement $p \implies q$ is True.

4. You do not get an A (p is False) and I do not buy you a pizza (q is False).

   Again, I did not break my promise. The condition of the promise was not met, so the promise was not violated. The statement $p \implies q$ is True.

This is often summarized as: "A false hypothesis implies anything." If the "if" part is false, the entire "if-then" statement is automatically considered true, regardless of the conclusion.

Converse, Inverse, and Contrapositive

From an original implication, we can form three other related "if-then" statements. It is crucial to understand that these new statements are not the same as the original.

Original Statement: If it is raining, then the ground is wet. ($p \implies q$)

1. The Converse (Swapping the parts)

The converse is formed by swapping the hypothesis and the conclusion.

Form: $q \implies p$

Example: "If the ground is wet, then it is raining."

Important: The converse is NOT logically equivalent to the original statement. Just because the ground is wet (perhaps from a sprinkler) doesn't mean it's raining.

2. The Inverse (Negating both parts)

The inverse is formed by negating both the original hypothesis and the original conclusion.

Form: $\sim p \implies \sim q$

Example: "If it is not raining, then the ground is not wet."

Important: The inverse is also NOT logically equivalent to the original statement. It might have just stopped raining, so the ground is still wet.

3. The Contrapositive (Swapping AND Negating)

The contrapositive is formed by negating both parts and then swapping them (like taking the inverse of the converse).

Form: $\sim q \implies \sim p$

Example: "If the ground is not wet, then it is not raining."

Crucial Point: The contrapositive IS logically equivalent to the original statement. They are just two different ways of saying the exact same thing. This is a vital tool in mathematics, as it is sometimes easier to prove the contrapositive of a theorem than to prove the original statement directly.

Truth Values of Conditional Statements

A conditional statement, or implication, is a compound statement of the form "If p, then q". The rules that determine its truth value are precise and form the basis of logical deduction in mathematics. In this section, we will also look at the "if and only if" statement, known as a biconditional.

Truth Table for Implication ($p \implies q$)

As discussed in the previous section, an implication is like a promise. The promise is only broken (i.e., the statement is false) if the initial condition is met but the promised outcome does not occur. This single scenario is the only one that results in a false implication.

The formal definition is captured in the following truth table:

The most important takeaway is that an implication is only false when a true hypothesis leads to a false conclusion. If the hypothesis is false to begin with, the implication is considered true by default, a principle often summarized as "from a falsehood, anything follows."

The Biconditional Statement ($p \iff q$)

A biconditional statement is written as "$p$ if and only if $q$" and is symbolized as $p \iff q$. This is a much stronger statement than a simple implication. It essentially means that $p$ and $q$ are locked together; they are either both true or both false.

It is logically the same as saying "(If p, then q) AND (If q, then p)".

Rule: The biconditional $p \iff q$ is true only when $p$ and $q$ have the same truth value.

For example, the statement "A triangle is equilateral if and only if it is equiangular" is true because if a triangle has equal sides, it must have equal angles, and if it has equal angles, it must have equal sides.

Negating a Conditional Statement

How do you contradict the promise "If it is raining, then I will carry an umbrella"? You don't do it by saying "If it is not raining, then I won't carry an umbrella." The only way to prove the promise is a lie is to show the one scenario where it fails: the hypothesis is true, but the conclusion is false.

Therefore, the negation of an "if p, then q" statement is an "and" statement.

The negation of $p \implies q$ is the statement "$p$ is true AND $q$ is false."

This is a very important equivalence in logic, especially for constructing proofs by contradiction.

Answer:

Answer:

Validating Statements

In mathematics, a statement is not accepted as fact until it has been rigorously validated. Validating a statement is the process of formally proving it to be either true or false. This process is the core of mathematical reasoning and distinguishes it from other fields of study. The method of validation depends heavily on the structure of the statement itself.

Proving "If-Then" Statements ($p \implies q$)

Many, if not most, mathematical theorems are conditional statements of the form "If [hypothesis], then [conclusion]". Proving such a statement means showing that whenever the hypothesis ($p$) is true, the conclusion ($q$) must also be true. There are several standard techniques to construct such a proof.

1. Direct Proof

This is the most straightforward method. The logic flows directly from the hypothesis to the conclusion.

Method:

1. Assume the hypothesis ($p$) is true. This is your starting point.
2. Use definitions, axioms, algebraic rules, and previously proven theorems to build a logical chain of deductions.
3. Show that this chain of logic inevitably leads to the conclusion ($q$) being true.

Example: Prove that if an integer $x$ is even, then $x^2$ is also even.

Proof: Assume $x$ is an even integer. By definition, this means $x = 2k$ for some integer $k$. Now, let's look at $x^2$. $x^2 = (2k)^2 = 4k^2 = 2(2k^2)$. Since $k$ is an integer, $2k^2$ is also an integer. Therefore, $x^2$ is of the form $2 \times (\text{an integer})$, which by definition means $x^2$ is even. Thus, we have proven that if $x$ is even, $x^2$ must be even.

2. Proof by Contrapositive

This is an indirect method that relies on a key logical equivalence: the statement "If $p$, then $q$" is exactly the same as "If not $q$, then not $p$". The second statement is called the contrapositive. Sometimes, it is much easier to prove the contrapositive directly.

Method:

1. Identify the contrapositive of the original statement: $\sim q \implies \sim p$.
2. Use a direct proof to prove this contrapositive statement.
3. Since the contrapositive is true, the original statement must also be true.

Example: Prove that if $x^2$ is an odd integer, then $x$ is an odd integer.

Proof: This is hard to prove directly. Instead, let's prove its contrapositive. The contrapositive is: "If $x$ is not an odd integer, then $x^2$ is not an odd integer." For integers, "not odd" means "even". So, we need to prove: "If $x$ is an even integer, then $x^2$ is an even integer." We already proved this is true using the direct proof method above. Since the contrapositive is true, the original statement must also be true.

3. Proof by Contradiction

This is another powerful indirect method. It works by assuming that the statement you want to prove is actually false, and then showing that this assumption leads to a logical impossibility or contradiction.

Method:

1. Assume the opposite of what you want to prove. For a statement $P$, assume $\sim P$ is true. For an implication $p \implies q$, assume it is false, which means you assume $p$ is true AND $q$ is false.
2. Follow a chain of logical deductions from this assumption.
3. Show that this chain leads to a contradiction (e.g., you prove that a number must be both even and odd, or that $1=0$).
4. Since your initial assumption led to an absurd result, the assumption must have been wrong. Therefore, the original statement must be true.

Example: Prove that $\sqrt{2}$ is an irrational number.

Proof: Assume the opposite: that $\sqrt{2}$ is a rational number. This means $\sqrt{2} = \frac{a}{b}$ where $a$ and $b$ are integers with no common factors. Squaring both sides gives $2 = \frac{a^2}{b^2}$, so $a^2 = 2b^2$. This means $a^2$ is even, which implies $a$ is even. So, we can write $a = 2k$. Substituting this back gives $(2k)^2 = 2b^2$, so $4k^2 = 2b^2$, which means $b^2 = 2k^2$. This means $b^2$ is even, which implies $b$ is also even. But if both $a$ and $b$ are even, they share a common factor of 2. This contradicts our initial assumption that $a$ and $b$ had no common factors. Our assumption must be false, therefore $\sqrt{2}$ must be irrational.

Disproving Statements with a Counterexample

To prove a statement is true, you need a general proof that covers all cases. However, to prove a statement is false, you only need to find one single case where it fails. This one case is called a counterexample.

This method works best for statements that make a "for all" or "every" claim.

Example: Disprove the statement "Every prime number is an odd number."

Disproof by Counterexample: We just need to find one prime number that is not odd. The number 2 is a prime number, and it is an even number, not an odd one. This single counterexample is sufficient to prove the statement is false.

Answer: